import java.util.*;

public class RemoveInvalidParentheses {

    StringBuilder stringBuilder;
    HashSet<String> set;
    public List<String> removeInvalidParentheses(String s) {
        stringBuilder = new StringBuilder();
        set = new HashSet<>();
        int countL = 0;
        int countR = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                ++countL;
            } else if (c == ')') {
                if (countL > 0) {
                    --countL;
                } else ++countR;
            }
        }
        dfs(s, 0, countL, countR);
        return new ArrayList<>(set);
    }

    public void dfs(String s, int i, int countL, int countR) {
        if (countL == 0 && countR == 0) {
            String temp = stringBuilder.toString() + s.substring(i);
            check(temp);
            return;
        }
        if (s.length() - i < (countL + countR)) return;
        stringBuilder.append(s.charAt(i));
        dfs(s, i + 1, countL, countR);
        stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        if (countL > 0 && s.charAt(i) == '(') {
            dfs(s, i + 1, countL - 1, countR);
        }
        if (countR > 0 && s.charAt(i) == ')') {
            dfs(s, i + 1, countL, countR - 1);
        }
    }

    public void check(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                ++count;
            } else if (s.charAt(i) == ')') --count;
            if (count < 0) return;
        }
        if (count == 0) set.add(s);
    }
}
